import time
import numpy as np

global index


def greedy_valueperweight(weight: list[int], values: list[int], volume: int):
    """
    :param weight:
    :param values:
    :param volume:
    :return:
    """
    global index
    x = [0 for _ in range(len(weight))]
    for i in range(len(weight)):
        x[i] = float(values[i] / weight[i])
    x.sort()
    print("按单位重量的价值排序为：", x)
    t = [0 for _ in range(len(weight))]
    for j in range(len(weight)):
        for i in range(len(weight)):
            if float(values[i] / weight[i]) == x[j]:
                t[j] = i
                break
    print("对应的原排列中的索引为：", t)
    sum_weight = 0
    sum_value = 0
    for index in range(len(weight) - 1, -1, -1):
        if sum_weight < volume and weight[t[index]] < volume - sum_weight:
            sum_value += values[t[index]]
            sum_weight += weight[t[index]]
        else:
            # print(index)
            break
    print("此时到了：", index)
    print("此时的总价值为：", sum_value)
    print("此时的总重量为：", sum_weight)
    res = volume - sum_weight
    print("剩余容量为：", res)
    sum_value = sum_value + res * float(values[t[index]] / weight[t[index]])
    print("最终结果为：", sum_value)


def main():
    count = int(np.random.randint(1, 15, 1))
    print("数量为：%d" % count)
    volume = int(np.random.randint(1, 15, 1))
    print("容量为：%d" % volume)
    each_weight = np.random.randint(1, 10, count).tolist()
    print("每个元素质量为:")
    print(each_weight)
    each_value = np.random.randint(1, 10, count).tolist()
    print("每个元素价值为:")
    print(each_value)
    time1 = time.perf_counter()
    greedy_valueperweight(each_weight, each_value, volume)
    time2 = time.perf_counter()
    print("消耗时间：%f s" % (time2 - time1))


if __name__ == '__main__':
    # weight = [1, 3, 4, 5, 1.5]
    # values = [3, 5, 6, 12, 7]
    weight = [35, 30, 75, 50, 40, 10, 25]
    values = [10, 40, 30, 50, 35, 40, 30]
    greedy_valueperweight(weight, values, 150)
    # main()
